import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class LetterCombinations {

    public static void main(String[] args) {
        LetterCombinations letterCombinations = new LetterCombinations();
        System.out.println(letterCombinations.letterCombinations("23"));
    }

    List<String> ans = new ArrayList<>();
    StringBuilder stringBuilder = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if (digits.equals("")) return new ArrayList<>();
        HashMap<Integer, String> map = new HashMap<>();
        map.put(2, "abc");
        map.put(3, "def");
        map.put(4, "ghi");
        map.put(5, "jkl");
        map.put(6, "mno");
        map.put(7, "pqrs");
        map.put(8, "tuv");
        map.put(9, "wxyz");

        process(map, digits, 0);
        return ans;
    }

    public void process(HashMap<Integer, String> map, String digits, int i) {
        if (i == digits.length()) {
            ans.add(stringBuilder.toString());
            return;
        }

        String s = map.get(digits.charAt(i) - 48);
        for (int j = 0; j < s.length(); j++) {
            String temp = s.charAt(j) + "";
            stringBuilder.append(temp);
            process(map, digits, i + 1);
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
    }
}
